The present invention relates to XML, and more particularly to achieving directed acyclic graph (DAG) representations of data in XML.
The omnipresence of the Internet in today""s society has created an expectation that desired information be readily available, easily accessible, and user-friendly. Conformance with established practices allows website designers and developers to meet the needs of Internet users. In general, hypertext markup language (HTML) was designed to display data, and to focus on how data looks. In a similar manner, extensible markup language (XML), was designed to describe data, and to focus on what data is.
XML provides a way to structure, store and send information and achieves a cross-platform, software- and hardware-independent tool for transmitting information. XML uses a DTD (Document Type Definition) to describe the constraints and define the valid elements of an XML document. Currently, XML capably represents data of a hierarchical data structure (xe2x80x98tree structurexe2x80x99), i.e., data with a traditional direct parent-child relationship, where each child has a single parent. Thus, an XML document can be represented as a tree of elements. A simple example of a hierarchical organization of information similar to the tree nature of XML documents is a file system, where files and folders are organized hierarchically, such that a folder may have files in it or other folders, and everything is descended from one root folder. Each file can be viewed as a child of the folder parent from which it descends.
There is no specific support in XML for representing data having a graph structure, e.g., a directed acyclic graph (DAG), where a child has multiple direct parents. Without support for a DAG, there is also no enforcement of the semantics of a DAG. For example, in a given situation, complex relationships may need to be represented, such as when a user of a system is associated as a member of several groups. A problem could exist in the specification of this type of relationship with XML.
FIGS. 1a and 1b illustrate circle graph diagrams for representing the example relationship where a user is a member of multiple groups. As shown in FIG. 1a, a choice could be made to represent a user 10 as a child of multiple parents, group 12 and group 14. Unfortunately, as stated above, XML only supports representation of a relationship where a child descends from a single parent. Thus, in order to represent the user 10 and its relationship to the multiple groups 12 and 14 in XML, the user 10 could become the parent for the individual children of groups 12 and 14, as shown in the diagram of FIG. 1b. In order to represent the relationships in this way, the semantics must be modified from xe2x80x9cusers belong to groupsxe2x80x9d to xe2x80x9cgroups belong to users.xe2x80x9d This reorganization, in which a user must designate the groups to which it belongs, is not optimal. While this choice as shown in FIG. 1b maintains a parent-child relationship that can be represented in XML, a problem arises when attempting to include other users that could exist for the groups 12 or 14. Having already been specified as children of user 10, they cannot be represented as children of another user, nor can the other users be their children without also descending from user 10.
As demonstrated by this example, a problem exists in XML in not being fully able to provide a more human-oriented manner of specifying data that accommodates situations where a DAG representation rather than a tree representation is appropriate.
Accordingly, what is needed is a generalized method and system for representing a directed acyclic graph (DAG) in a hierarchical XML information set. The present invention addresses such a need.
The present invention provides method and system aspects for achieving directed acyclic graph (DAG) representations of data in XML. The aspects include augmenting a document type definition (DTD) for allowing description of the DAG in an XML file and for providing an API for processing the DAG transparently. The API is consistent with and interoperates with the standard document object model application program interface (DOM API) for processing the XML file.
According to the system and method disclosed herein, a more human-oriented way of specifying data relationships within the hierarchical structure of XML is achieved. The data specification allows an element to be specified initially with subsequent references linked to the initial specification. Further, the present invention provides the functions necessary to properly process the new data definitions in a seamless and straightforward manner.